1. Field of the Invention
The present invention relates to a method for decreasing the number of input terminals used in an operator that employs an exchange principle, and more particularly to an improved method for minimizing the number of input terminals used in an operator/operand by employing a graph coloring algorithm.
2. Description of the Related Art
In recent years, semiconductor devices have been widely applied to a variety of industrial fields including the information communication field. With significantly enhanced semiconductor device fabrication techniques, chip integration is being further improved. However, there still remain a few problems to be solved in order to achieve larger scaled integration.
One of the unsolved problems in the conventional semiconductor device fabrication techniques is providing an effective method for decreasing the number of input terminals or wirings used in different operators, e.g., logic gates.
With reference to FIGS. 1 and 2, a conventional method for designing an input wirework of an algorithm-performing operator will now be described.
In the conventional method, an adder is required to process a plurality of data values outputted from data sources different from each other as shown in FIG. 1. With regard to a plurality of control steps that are also different from each other, a hardware composition according to the conventional art as shown in FIG. 2 employs a 3.times.1 multiplexer 1 for receiving data values D1, D2 and D4, a 3.times.1 multiplexer 2 for receiving data values D1, D2 and D3, and an adder 3 for receiving the output from each multiplexer 1 and 2 to generate output data DO. However, in such an operator according to the conventional art, an adoption of an exchange principle is not considered in the interconnection design, and thus a larger number of input terminals (i.e., 6 input terminals of the multiplexers 1 and 2) are needed.
Further, although the number of input terminals used in the operator may be decreased by exchanging data pairs, this decreasing operation according to the conventional art is limited to a partial reduction of the input terminals, so there still exists a difficult problem to be solved to efficiently realize a larger scaled integration with regard to operator input terminals.